package main

import "fmt"

/*
数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。
请注意，你需要找的是数组排序后的第
k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
 */

// 快速排序
func findKthLargest(nums []int, k int) int {
	quick(nums, 0, len(nums) - 1)
	fmt.Println(nums)
	return nums[len(nums) - k]
}

func quick(num []int, left, right int)  {
	if left > right {
		return
	}
	val := num[left]
	k := left
	for i := left + 1; i <= right; i ++ {
		if num[i] < val {  // 交换
			num[k] = num[i]
			num[i] = num[k + 1]
			k ++
		}
	}
	num[k] = val
	quick(num, left, k - 1)
	quick(num, k + 1, right)
}

func main() {
	fmt.Println(findKthLargest([]int{3,2,1,5,6,4}, 2))
}
